忍者ブログ

競プロ日記

競技プログラミングの問題を解いた感想を書きます。

[PR]
×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

ABC017 D サプリメント
コード
https://abc017.contest.atcoder.jp/submissions/3789176


競プロ初記事は初心者らしくACできない記事。
解説見ながらとりあえず愚直に書いてTLE。
しゃくとり法使って書くも、既に出てきた数字を探すのにfind使ったせいでどうも遅いが一応AC。
納得できずに高速化を図るもACが出ない。←今ココ
単純にdpの更新方法の認識が間違っている気がするけど、一度ACできた=アルゴリズムは間違っていないはず。
もう手が出ない。



12/15 6:00追記
AC取れた。
https://abc017.contest.atcoder.jp/submissions/3789283

サプリメントの総数N<サプリメントの種類Mがあり得るということか。
味の種類とはいえ普通総数の中で数えるだろう・・・。
確かにN≧Mとは書いていないけれど、これは単純に文脈から読み取れる内容ではないのか。
学校のテストならさすがに文句言いに行くレベル。

気づけたのはなんとなくVectorの要素数を最大限まで持っていった場合になぜかAC取れたから。
とりあえず配列系は要素数最大まで取るのが正義なのだろうか。
累積和使ってさらに高速化もしてみたいけどまた今度。
PR

コメント

コメントを書く